On the Computability of Solomonoff Induction and Knowledge-Seeking

摘要

Solomonoff induction is held as a gold standard for learning, but it is knownto be incomputable. We quantify its incomputability by placing various flavorsof Solomonoff's prior M in the arithmetical hierarchy. We also derivecomputability bounds for knowledge-seeking agents, and give a limit-computableweakly asymptotically optimal reinforcement learning agent.